#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <memory>

using namespace std;

class Matrix
{
    public :
        inline unsigned int getSize() const
        {
            return _vvMatrix.size();
        }

        inline double get(const unsigned int &x, const unsigned int &y) const
        {
            return _vvMatrix[x][y];
        }

        void set(unsigned int x, unsigned int y, double d)
        {
            _vvMatrix[x][y] = d;
            _vvMatrix[y][x] = d;
        }

        void randomGen3(unsigned int size, double maxDelta)
        {
            _vvMatrix.resize(size);
            for (unsigned int i = 0; i < _vvMatrix.size(); i++)
                _vvMatrix[i].resize(size);


            for (unsigned int i = 1; i < size; i++)
                for (unsigned int j = 0; j < (size-i); j++)
                    set(i+j, j, abs((int)((rand() % (int)(5+maxDelta*2)) + max( get(i+j-1, j), get(i+j, j+1) ) - maxDelta)) );


            std::vector<unsigned int> totalOrder;
            for (unsigned int i = 0; i < size; i++)
                totalOrder.push_back(i);
        }

        void randomGen2(unsigned int size)
        {
            _vvMatrix.resize(size);
            for (unsigned int i = 0; i < _vvMatrix.size(); i++)
                _vvMatrix[i].resize(size);

            for (unsigned int i = 0; i < size; i++)
                for (unsigned int j = i+1; j < size; j++)
                    set(i, j, (int)(rand() % 100));
        }

        void randomGen(unsigned int size)
        {
            std::pair<unsigned int, unsigned int> points[size];
            for (unsigned int i = 0; i < size; i++)
            {
                points[i].first =  (rand() % 100);
                points[i].second = (rand() % 100);
            }

            _vvMatrix.resize(size);
            for (unsigned int i = 0; i < _vvMatrix.size(); i++)
                _vvMatrix[i].resize(size);


            for (unsigned int i = 0; i < size; i++)
                for (unsigned int j = i+1; j < size; j++)
                    set(i, j, (int)sqrt(
                                (points[i].first - points[j].first)*(points[i].first - points[j].first) +
                                (points[i].second - points[j].second)*(points[i].second - points[j].second)));
        }

        //private :
        std::vector<std::vector<double> > _vvMatrix;
};


std::ostream& operator << (std::ostream& os, const Matrix& m) 
{
    os << m.getSize() << endl;
    for (unsigned int i = 0; i < m.getSize(); i++)
    {
        for (unsigned int j = 0; j < m.getSize(); j++)
            os << m.get(i,j) << "\t";
        os << endl;
    }
    return os; 
}



std::istream& operator >> (std::istream& is, Matrix& m)
{
    unsigned int size;
    is >> size;

    m._vvMatrix.resize(size);
    for (unsigned int i = 0; i < m._vvMatrix.size(); i++)
        m._vvMatrix[i].resize(size);

    for (unsigned int i = 0; i < m._vvMatrix.size(); i++)
        for (unsigned int j = 0; j < size; j++)
        {
            double d;
            is >> d;
            m.set(i, j, d);
        }

    return is;
}


double calculateDelta( const Matrix &m )
{
    Matrix result = m;
    double delta;

    double vXY;
    unsigned int x;

    for (unsigned int fx = m.getSize()-1; fx > 1; fx--)
    {
        for (unsigned int y = 0; y < (m.getSize()-fx); y++)
        {
            x = fx+y;
            vXY = result.get( x, y );
            if( result.get( x-1, y) > vXY )
                result.set( x-1, y, vXY);
            if( result.get( x,   y+1) > vXY )
                result.set( x,   y+1, vXY);
        }
    }

    double maxDiff=0;
    for (unsigned int x = 0; x < m.getSize(); x++)
        for (unsigned int y = x+1; y < m.getSize(); y++)
        {
            if( maxDiff < (m.get( x, y ) - result.get(x, y) ))
                maxDiff = m.get( x, y ) - result.get(x, y);
        }

    delta = (maxDiff/2.0);
    /*
       for (unsigned int x = 0; x < m.getSize(); x++)
       for (unsigned int y = x+1; y < m.getSize(); y++)
       result.set( x, y, result.get(x, y) + delta );
       */
    return delta;
}

void showHelp(std::string a)
{
    std::cerr << "usage: \t";
    std::cerr << "\t" << a;
    std::cerr << " [(-g 1 size) || (-g 2 size) || (-g 3 size maxDelta)]";
    std::cerr << " [-o output-file]";
    std::cerr << std::endl;

    std::cerr << "\t-g 1 size : Generate 'size' random point in a plan 100x100 and create matrix with distance off any point." << std::endl;
    std::cerr << "\t-g 2 size : Generate random matix" << std::endl;
    std::cerr << "\t-g 3 size maxDelta : Generate random matrix such as delta <= maxDelta" << std::endl;
}



void showErrorSyntax(std::string a)
{
    std::cerr << "Syntax error" << std::endl;
    showHelp(a);
    exit(-1);
}

int main(int argc, char const* argv[])
{
    Matrix m;
    std::auto_ptr<std::ostream> OUT( NULL );
    int pos=1;

    srand(time(0));

    while(pos < argc)
    {
        if( (strlen(argv[pos]) != 2) || (argv[pos][0] != '-') )
            showErrorSyntax(argv[0]);

        switch( argv[pos][1] )
        {
            case 'O' :
            case 'o' :
                if(OUT.get() != NULL)
                    showErrorSyntax(argv[0]);

                OUT.reset( new std::ofstream( argv[pos+1] ) ) ;

                pos+=2;
                break;

            case 'G' :
            case 'g' :
                if( m.getSize()>0 )
                    showErrorSyntax(argv[0]);

                unsigned int algo;
                {
                    std::istringstream iss( argv[pos+1] );
                    iss >> algo;
                }
                unsigned int size;
                {
                    std::istringstream iss( argv[pos+2] );
                    iss >> size;
                }
                switch(algo)
                {
                    case 1 :
                        m.randomGen( size );
                        pos+=3;
                        break;

                    case 2 :
                        m.randomGen2( size );
                        pos+=3;
                        break;

                    case 3 :
                        unsigned int deltaMax;
                        {
                            std::istringstream iss( argv[pos+3] );
                            iss >> deltaMax;
                        }
                        m.randomGen3( size, deltaMax );
                        pos+=4;
                        break;

                    default :
                        showErrorSyntax(argv[0]);
                }

                break;

            case 'h' :
            case 'H' :
                showHelp(argv[0]);
                return 0;

            default :
                showErrorSyntax(argv[0]);
        }
    }

    if( m.getSize() == 0 )
        showErrorSyntax(argv[0]);


    if(OUT.get() != NULL)
        *OUT << m << std::endl;
    else
        std::cout << m << std::endl;

    return 0;
}
